// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	int top;		// 栈顶 (有效元素个数)
	int capacity;  // 容量 
}Stack;

typedef struct {
    Stack S1;       //队尾
    Stack S2;       //队头
} MyQueue;

// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->capacity = 3;  //?
	ps->top = 0;
	ps->arr = (STDataType*)malloc(sizeof(STDataType)* ps->capacity);
	if (NULL == ps->arr){
		assert(0);     //申请空间失败断言
		return;
	}
}

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	if (ps->arr){    //栈 不为空
		free(ps->arr);
		ps->arr = NULL;
		ps->capacity = 0;
		ps->top = 0;
	}
}

//检查capacity,扩容
static void CheckCapacity(Stack* ps)
{
	assert(ps);
	if (ps->top == ps->capacity){         //栈满
		int newcapacity = 2 * (ps->capacity);
		//1.开辟新空间
		STDataType* temp = (STDataType*)malloc(sizeof(STDataType) * newcapacity);
		if (NULL == temp){
			assert(0);
			return;
		}
		//2.拷贝元素
		memcpy(temp, ps->arr, sizeof(STDataType)*ps->top);
		//3.释放旧空间,使用新空间
		free(ps->arr);
		ps->arr = temp;
		ps->capacity = newcapacity;
	}
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	/*if (ps->arr){
		return 0;
	}
	return -1;*/
	return 0 == ps->top;
}

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	CheckCapacity(ps);
	ps->arr[ps->top] = data;
	(ps->top)++;
}

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	if (!StackEmpty(ps)){      //栈不为空
		ps->top--;
	}
}

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(!StackEmpty(ps));     //栈不为空，才有栈顶元素，为空则触发断言
	if (ps->arr){
		return ps->arr[ps->top - 1];
	}
    return 0;
}

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);
	if (ps->arr){
		return ps->top;
	}
	return 0;
}

MyQueue* myQueueCreate() {
    MyQueue* mq = (MyQueue*)malloc(sizeof(MyQueue));    //申请结构空间
    if(NULL == mq){
        return NULL;
    }
    StackInit(&mq->S1);
    StackInit(&mq->S2);
    return mq;
}

//入队
void myQueuePush(MyQueue* obj, int x) {
    //队尾入队（S1入栈）
    StackPush(&obj->S1, x);       
}

//队列的开头移除并返回元素
int myQueuePop(MyQueue* obj) {
    /*
    int ret;
    if(!StackEmpty(&obj->S1)){    //如果S1不为空
        while(StackSize(&obj->S1) - 1){   //将S1中n-1个元素移到S2中
            StackPush(&obj->S2, StackTop(&obj->S1));
            StackPop(&obj->S1);
        }
        num = StackTop(&obj->S1);        //得到S1的栈顶元素（队头）
        StackPop(&obj->S1);              //删除S1栈顶
        while(StackSize(&obj->S2)){      //再将S2中所有元素移回S1
            StackPush(&obj->S1, StackTop(&obj->S2));
            StackPop(&obj->S2);
        }
    }
    */

    if(StackEmpty(&obj->S2)){   //s2为空
        while(!StackEmpty(&obj->S1)){
            //S1不为空将S1中元素移到S2
            StackPush(&obj->S2, StackTop(&obj->S1));
            StackPop(&obj->S1);
        }
    }
    int ret = StackTop(&obj->S2);
    StackPop(&obj->S2);   //出队
    return ret;
}

//返回队列开头的元素
int myQueuePeek(MyQueue* obj) {
    /*
    int num;
    if(!StackEmpty(&obj->S1)){
        while(StackSize(&obj->S1) - 1){
            StackPush(&obj->S2, StackTop(&obj->S1));
            StackPop(&obj->S1);
        }
        num = StackTop(&obj->S1);
        while(StackSize(&obj->S2)){
            StackPush(&obj->S1, StackTop(&obj->S2));
            StackPop(&obj->S2);
        }
    }
    else{
        while(StackSize(&obj->S2) - 1){
            StackPush(&obj->S1, StackTop(&obj->S2));
            StackPop(&obj->S2);
        }
        num = StackTop(&obj->S2);
        while(StackSize(&obj->S1)){
            StackPush(&obj->S2, StackTop(&obj->S1));
            StackPop(&obj->S1);
        }
    }
    return num;
    */

    if(StackEmpty(&obj->S2)){   //s2为空
        while(!StackEmpty(&obj->S1)){
            //S1不为空将S1中元素移到S2
            StackPush(&obj->S2, StackTop(&obj->S1));
            StackPop(&obj->S1);
        }
    }

    return StackTop(&obj->S2);;
}

bool myQueueEmpty(MyQueue* obj) {
    //两个栈都为空 ，队列空
    return StackEmpty(&obj->S1) && StackEmpty(&obj->S2);
}

void myQueueFree(MyQueue* obj) {
    if(obj){
        StackDestroy(&obj->S1);
        StackDestroy(&obj->S2);

        free(obj);
    }
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/